package me.eg.ten;

import java.util.*;

/**
 * 136. 邻值查找
 * <p>
 * 给定一个长度为 n 的序列 A，A 中的数各不相同。
 * <p>
 * 对于 A 中的每一个数 Ai，求：
 * <p>
 * min1≤j<i|Ai−Aj|
 * 以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。
 * <p>
 * 输入格式
 * 第一行输入整数 n，代表序列长度。
 * <p>
 * 第二行输入 n 个整数A1…An,代表序列的具体数值，数值之间用空格隔开。
 * <p>
 * 输出格式
 * 输出共 n−1 行，每行输出两个整数，数值之间用空格隔开。
 * <p>
 * 分别表示当 i 取 2∼n 时，对应的 min1≤j<i|Ai−Aj| 和 Pi 的值。
 * <p>
 * 数据范围
 * n≤10^5,|Ai|≤10^9
 * <p>
 * 链接：https://www.acwing.com/problem/content/description/138/
 */
public class Search {
    public void search() {
        // 输入
        int[] nums = in();

        // 求解
        List<int[]> ans = search(nums);

        // 输出
        out(ans);
    }

    private List<int[]> search(int[] nums) {
        int n = nums.length;
        // 1. 初始化排序列表
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            treeMap.put(nums[i], i + 1);
        }

        // 2. 问题求解
        LinkedList<int[]> ans = new LinkedList<>();
        for (int i = n; i > 1; i--) {
            int value = nums[i - 1];
            Map.Entry<Integer, Integer> higherEntry = treeMap.higherEntry(value); // 后继
            Map.Entry<Integer, Integer> lowerEntry = treeMap.lowerEntry(value); // 前驱
            if (lowerEntry == null || (higherEntry != null && higherEntry.getKey() - value < value - lowerEntry.getKey())) {
                ans.offerFirst(new int[]{higherEntry.getKey() - value, higherEntry.getValue()});
            } else {
                ans.offerFirst(new int[]{value - lowerEntry.getKey(), lowerEntry.getValue()});
            }
            // 该节点求解完成，删除，不影响后面的前驱后继计算
            treeMap.remove(value);
        }
        return ans;
    }

    private int[] in() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        return nums;
    }

    private void out(List<int[]> list) {
        for (int[] line : list) {
            System.out.println(line[0] + " " + line[1]);
        }
    }

    public static void main(String[] args) {
        Search s = new Search();
        s.search();
    }
}
